BZOJ1061【NOI2008】志愿者招募 <线性规划转费用流>

Problem

【NOI2008】志愿者招募

Description

申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。
经过估算，这个项目需要天才能完成，其中第天至少需要个人。布布通过了解得知，一共有类志愿者可以招募。其中第类可以从第天工作到第天，招募费用是每人元。
新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。

Input

第一行包含两个整数，表示完成项目的天数和可以招募的志愿者的种类。
接下来的一行中包含个非负整数，表示每天至少需要的志愿者人数。
接下来的行中每行包含三个整数，含义如上文所述。
为了方便起见，我们可以认为每类志愿者的数量都是无限多的。

Output

仅包含一个整数，表示你所设计的最优方案的总费用。

Sample Input

Sample Output

HINT

，，题目中其他所涉及的数据均不超过。

标签：线性规划 费用流

Solution

经典线性规划转网络流。

由题意可知，共会有个限制条件，还有一个需要最小化的表达式。以样例作例子，第种招募人，则有

接着设三个辅助变量，使得

在最前面和最后面加入两个，差分一下，得到

发现每个变量只出现两次，并且正、负各一次。这个性质其实一定成立。因为每种志愿者只在一个区间内出现，即每个变量只会在连续的式子中出现，这样差分后就会只剩一次正和一次负。辅助变量也有这个性质是显然的。
如果将每个式子看成一个结点，等式可以看作这个点的流量平衡方程。将正看成出流，负看成入流，即可构图。例如，对于，其在第二个式子中出现正，在第四个式子中出现负，可以想成是从二号结点流出的流量进入四号结点。对于辅助变量也是一样。而对于每个式子中的常数项，可以看成从源点流出或流入汇点，即若移到左边后为负，则为从源点流出这么多流量；若为正，则为向汇点流这么多流量。
这样一来，根据费用流一定跑出最大流（废话），跑出的流一定满足流量平衡方程（废话2），最后跑出的方案一定能满足所有限制。如果加上边权（即所要取最小值的式子的系数），可以跑最小费用最大流解出最小值。

建模：

对于，
- 若，连接，容量，单位费用
- 若，连接，容量，单位费用
对于一种志愿者，连接，容量，单位费用
辅助变量：对于，连接，容量，单位费用

跑最小费用最大流即可。

Code

#include <bits/stdc++.h>
#define MAX_N 2000
#define MAX_M 50000
#define INF 0x3f3f3f3f
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, s, t, cnt, pr[MAX_N+5], cr[MAX_N+5], mxf, mic;
struct node {int v, c, w, nxt;} E[MAX_M+5]; int a[MAX_N+5];
void init() {s = 0, t = n+2, cnt = 0, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c, int w) {E[cnt] = (node){v, c, w, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c, int w) {insert(u, v, c, w), insert(v, u, 0, -w);}
bool SPFA() {
    queue <int> que; bool inq[MAX_N+5]; int d[MAX_N+5], cr[MAX_N+5];
    memset(inq, false, sizeof inq), memset(d, INF, sizeof d);
    d[s] = 0, que.push(s), inq[s] = true, memset(cr, -1, sizeof cr);
    while (!que.empty()) {
        int u = que.front(); que.pop(), inq[u] = false;
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c, w = E[i].w;
            if (c && d[u]+w < d[v]) {
                d[v] = d[u]+w, cr[v] = i;
                if (!inq[v]) que.push(v), inq[v] = true;
            }
        }
    }
    if (d[t] == INF) return false;	int flow = INF;
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) flow = min(flow, E[i].c);
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) E[i].c -= flow, E[i^1].c += flow;
    mxf += flow, mic += d[t]*flow;	return true;
}
int main() {
    read(n), read(m), init();
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int i = 1; i <= n+1; i++)
        if (a[i] >= a[i-1]) addedge(s, i, a[i]-a[i-1], 0);
        else addedge(i, t, a[i-1]-a[i], 0);
    for (int i = 1, u, v, w; i <= m; i++)
        read(u), read(v), read(w), addedge(u, v+1, INF, w);
    for (int i = 2; i <= n+1; i++) addedge(i, i-1, INF, 0);
    while (SPFA()) ;	return printf("%d\n", mic), 0;
}